package com.coderman.topn;

import java.util.Random;

/**
 * @Author fanchunshuai
 * @Date 2019/11/23 17
 * @Description:
 * 面试题目：如何在10亿个整数中找出前1000个最大的数。
 * 模拟超过1亿随机数，从中找出最大的N个数
 * 构建小顶堆：
 * 小顶堆的性质如下：每一个父节点的值都小于左右孩子节点，然后依次从文件中读取10亿个整数，
 * 如果元素比堆顶小，则跳过不进行任何操作，如果比堆顶大，则把堆顶元素替换掉，并重新构建小顶堆。
 * 当10亿个整数遍历完成后，堆内元素就是TopN的结果。
 * https://blog.csdn.net/nuowei_senlin/article/details/86734931
 *
 */
public class TopNNumber {
    public static int N = 10;
    public static int LEN = 100000000;
    public static int arrs[] = new int[LEN];
    public static int arr [] = new int[N];

    //数组长度
    public static int len = arr.length;

    //堆中元素的有效元素 heapSize <= len
    public static int heapSize = len;

    public static void main(String[] args) {
        Random random = new Random();
        //生成随机数组
        for (int i = 0;i < LEN;i ++){
            arrs[i] = random.nextInt(999999999);
        }
        //构建初始堆
        for (int i = 0 ;i < N;i ++){
            arr[i] = arrs[i];
        }

        long start = System.currentTimeMillis();
        buildMinHeap();
        for (int i = N ;i < LEN;i ++){
            if(arrs[i] > arr[0]){
                arr[0] = arrs[i];
                minHeap(0);
            }
        }
        long end = System.currentTimeMillis();

        System.out.println(LEN +"个数,求Top"+N+",耗时"+(end - start));
        print();

    }






    /**
     * 自低向上构建小堆
     */
    public static void buildMinHeap(){
        int size = len / 2;
        for (int i = size;i >= 0;i --){
            minHeap(i);
        }
    }


    /**
     * i节点为根及子树是一个小堆
     * @param i
     */
    public static void minHeap(int i ){
        int l = left(i);
        int r = right(i);
        int index = i;
        if(l < heapSize  && arr[l] < arr[index]){
            index = l;
        }
        if(r < heapSize && arr[r] < arr[index]){
            index = r;
        }

        if(index != i){
            int t = arr[index];
            arr[index] = arr[i];
            arr[i] = t;
            //递归向下构建堆
            minHeap(index);
        }
    }


    /**
     * 返回i节点的左孩子
     * @param i
     * @return
     */
    public static int left(int i){
        return 2 * i;
    }

    /**
     * 返回i节点的右孩子
     * @param i
     * @return
     */
    public static int right(int i){
        return 2 * i + 1;
    }



    /**
     * 打印堆
     */
    public static void  print(){
        for (int a : arr){
            System.out.print(a+",");
        }
        System.out.println();
    }

}
